Mass-storage devices such as disk drives, compact disks, DVD's, etc., tend to develop media defects over time, which cause data errors. Communication systems such as wireless networks, satellite broadcast systems, xDSL modems, etc., experience data errors caused by noise, interference, etc. Numerous error-correcting techniques such as Reed-Solomon (RS) coding are used to correct such errors.
Referring now to FIG. 1A, a RS code-based error-correcting system 10 includes a RS encoder 12 that receives a block of digital data from a data source such as a communication system (not shown). The RS encoder 12 adds redundant check-bytes to the block of digital data. The combined data is transmitted via a communication channel 14 such as a transmission line or a wireless link. The data may also be stored in a mass-storage device 15 such as a disk drive. Errors may occur during transmission or storage of the data due to noise, interference, media defects, etc. A RS decoder 16 decodes each block of data and attempts to correct errors and recover the original data. The number and type of errors that can be corrected depend on the characteristics of the RS code.
In an error-correcting scheme that uses RS codes, a polynomial is constructed using data symbols (e.g., data bytes) that are to be transmitted. An over-sampled plot of the polynomial is transmitted instead of transmitting the data symbols. Because the transmitted data is over-sampled with redundant information, the polynomial and the data symbols can be substantially reconstructed when received despite transmission errors.
Typically, the scheme encodes the data in a data block as points of a polynomial plotted over a finite field. The coefficients of the polynomial are the data symbols of the data block. The plot over-determines the coefficients, which can be recovered from subsets of the plotted points. Just as a curve can be corrected by interpolating past a gap, a RS code can bridge a series of errors in the data block to recover the coefficients of the polynomial.
Specifically, if the system 10 uses a RS(N,K) code, the RS encoder 12 receives a block of data comprising K message bytes. The RS encoder 12 adds R redundant bytes to the data to generate an N-byte codeword, where R=N−K. The error-correcting ability of the RS(N,K) code is a function of the redundancy R. For example, the RS decoder 16 using the RS(N,K) code can correct up to R/2 bytes that may contain errors. That is, the RS code can correct half as many erroneous bytes as the number of redundant bytes that are added to the data block.
Errors in systems such as mass-storage devices, communication systems, etc., generally occur in the form of Additive White Gaussian Noise (AWGN) and in bursts. The RS code is frequently used to correct errors in these systems. When errors occur in bursts and the number of errors in a codeword exceeds R/2, the RS decoder 16 may fail to correct the errors. Some systems use an interleaver and a de-interleaver between the RS encoder 12 and the RS decoder 16 to improve error-correction capability of the RS decoder 16.
Referring now to FIG. 1B, an interleaver 13 with an interleave depth D spreads a block of N consecutive bytes of a RS codeword evenly into D*N bytes before transmission. A de-interleaver 17 de-spreads the D*N bytes back into the N consecutive bytes of the block. If the communications channel 14 encounters a burst error of B bytes, the de-interleaver 17 de-spreads the B bytes of the burst error evenly into shorter bursts each of length B/D. Thus, each RS codeword encounters only B/D bytes of errors. That is, the interleaver 13 of depth D effectively cuts the longer burst into shorter bursts by a factor of D. If B/D is less than R/2, the RS decoder 16 can correct all the burst errors. If B/D is larger than R/2, however, the RS decoder 16 can not correct the burst errors.
One way to solve this problem is to increase the interleaver depth D. For example, D can be increased up to 4096 in some modern systems such as VDSL2. The cost of hardware, however, to implement such an interleaver may be very high. Additionally, the hardware that implements such an interleaver may significantly increase latency delay, which may degrade system performance.
Referring now to FIGS. 2-3, some exemplary implementations of the decoding and error-correcting scheme that uses the interleaver and de-interleaver are shown. Referring now to FIG. 2, a mass-storage device 20 such as a disk drive communicates with a host adapter 22. The host adapter 22 transmits data that is to be stored in the storage device 20. An encoder 24 in the storage device 20 uses a coding scheme such as RS coding to encode the data. An interleaver 25 interleaves RS codewords. A read/write preamplifier 26 amplifies the encoded and interleaved data. A read/write element (not shown) writes the amplified data on a recording medium 28 of the storage device 20.
To retrieve the data stored in the storage device 20, the host adapter 22 sends a read request to the storage device 20. The read/write element reads the data from the recording medium 28. The read/write preamplifier 26 amplifies the data. A de-interleaver 29 de-spreads the data back into consecutive RS codewords. A decoding and error correcting module 30 decodes the data and corrects any errors in the data. The storage device 20 transmits the data to the host adapter 22.
In recent years, data-density, spin rates, and throughput rates of mass-storage devices have been steadily increasing. Accordingly, designing the devices with fast and accurate interleaving, decoding, and error-correcting schemes is becoming increasingly important to ensure data reliability.
Referring now to FIG. 3, a high-speed, high-bandwidth communication system 50 utilizes a Very high bit-rate Digital Subscriber Line (VDSL) or VDSL2 to transport data. The system 50 comprises a VDSL/VDSL2 host computer 52, a VDSL/VDSL2 transceiver 54, and multiple subscribers 56-1, . . . , 56-N (collectively 56).
The VDSL/VDSL2 transceiver 54 utilizes a discrete multi-tone (DMT) carrier system to transport data between the VDSL/VDSL2 host computer 52 and the subscribers 56. A DMT module 58 controls the DMT carrier system. An encoder 60 encodes data from the VDSL/VDSL2 host computer 52. An interleaver 59 interleaves RS codewords into dispersed version before the data is transmitted to the subscribers 56. A de-interleaver 61 de-spreads the data received from the subscribers 56 back into consecutive RS codewords. A decoding and error-correcting module 62 decodes data received from de-interleaver 61 and corrects any errors in the received data. The decoded data is forwarded to the VDSL/VDSL2 host computer 52.
The DMT module 58 divides a very wide spectrum of signal received from a subscriber 56 into many separate 4 KHz sub-channels. For example, an ADSL system can divide a spectrum of 1 MHz spectrum into 256 sub-channels each of 4-KHz. Some of the 256 channels may transport data in one direction while others may transport data in the reverse direction (i.e., upstream and downstream) between the VDSL/VDSL2 transceiver 54 and the subscribers 56. Additionally, the DMT module 58 monitors each channel and searches for the best channels to transmit and receive data. If quality of one channel is impaired due to high error rates, the DMT module 58 shifts a signal to another channel.
For VDSL/VDSL2 to function effectively and deliver designed performance, the DMT carrier system requires that the data received from multiple channels be decoded and reconstructed speedily and accurately. To achieve this goal using traditional interleaving, decoding, and error-correcting techniques, extensive hardware may be required. Using extensive hardware can increase system cost and system latency delay. VDSL2, which transports data at speeds of up to 100 Mbps upstream and 100 Mbps downstream, demands even higher decoding and error-correcting capabilities than VDSL.